SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Expression problem</title>

</head>

Expression problem

</h1>

</header>

The expression problem is a challenging problem in <a href="Programming_language" title="Programming language">programming languages</a> that concerns the extensibility and modularity of statically typed data abstractions. The goal is to define a data abstraction that is extensible both in its representations and its behaviors, where one can add new representations and new behaviors to the data abstraction, without recompiling existing code, and while retaining static type safety (e.g., no casts). The statement of the problem exposes deficiencies in <a href="Programming_paradigm" title="Programming paradigm">programming paradigms</a> and <a href="Programming_language" title="Programming language">programming languages</a>. Philip Wadler, one of the co-authors of Haskell, has originated the term.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<a href="Philip_Wadler" title="Philip Wadler">Philip Wadler</a> formulated the challenge and named it "The Expression Problem"<a href="#cite_note-WadlerPost-1">[1]</a> in response to a discussion with Rice University's <a href="Racket_(programming_language)#Development" title="Racket (programming language)">Programming Languages Team (PLT)</a>.

He also cited three sources that defined the context for his challenge:

The problem was first observed by <a href="John_C._Reynolds" title="John C. Reynolds">John Reynolds</a> in 1975.<a href="#cite_note-Reynolds-2">[2]</a> Reynolds discussed two forms of Data Abstraction: User-defined Types, which are now known as <a href="Abstract_data_types" class="mw-redirect" title="Abstract data types">Abstract Data Types</a> (ADTs) (not to be confused with <a href="Algebraic_data_types" class="mw-redirect" title="Algebraic data types">Algebraic Data Types</a>), and Procedural Data Structures, which are now understood as a primitive form of Objects with only one method. He argued that they are complementary, in that User-defined Types could be extended with new behaviors, and Procedural Data Structures could be extended with new representations. He also discussed related work going back to 1967.

Fifteen years later in 1990, <a href="William_Cook_(computer_scientist)" title="William Cook (computer scientist)">William Cook</a><a href="#cite_note-CookOOPvsADT-3">[3]</a>

applied Reynold's idea in the context of Objects and Abstract Data Types, which had both grown extensively. Cook identified the matrix of representations and behaviors that are implicit in a Data Abstraction, and discussed how ADTs are based on the behavioral axis, while Objects are based on the representation axis. He provides extensive discussion of work on ADTs and Objects that are relevant to the problem. He also reviewed implementations in both styles, discussed extensibility in both directions, and also identified the importance of static typing.

Most importantly, he discussed situations in which there was more flexibility than

Reynolds considered, including internalization and optimization of methods.

At ECOOP '98, <a href="Shriram_Krishnamurthi" title="Shriram Krishnamurthi">Shriram Krishnamurthi</a> et al.<a href="#cite_note-Synth-4">[4]</a> presented a design pattern solution to the problem of simultaneously extending an expression-oriented programming language and its tool-set. They dubbed it the "expressivity problem" because they thought programming language designers could use the problem to demonstrate the expressive power of their creations. For PLT, the problem had shown up in the construction of DrScheme, now <a href="Racket_(programming_language)#DrRacket_IDE" title="Racket (programming language)">DrRacket</a>, and they solved it<a href="#cite_note-FF-5">[5]</a> via a rediscovery of <a href="Mixin" title="Mixin">mixins</a>.<a href="#cite_note-Mixins-6">[6]</a><a href="#cite_note-FKF-7">[7]</a> To avoid using a programming language problem in a paper about programming languages, Krishnamurthi et al. used an old geometry programming problem to explain their pattern-oriented solution. In conversations with Felleisen and Krishnamurthi after the ECOOP presentation, Wadler understood the PL-centric nature of the problem and he pointed out that Krishnamurthi's solution used a cast to circumvent Java's type system. The discussion continued on the types mailing list, where Corky Cartwright (Rice) and <a href="Kim_Bruce" title="Kim Bruce">Kim Bruce</a> (Williams) showed how type systems for OO languages might eliminate this cast. In response Wadler formulated his essay and stated the challenge, "whether a language can solve the expression problem is a salient indicator of its capacity for expression." The label "expression problem" puns on expression = "how much can your language express" and expression = "the terms you are trying to represent are language expressions".

Others co-discovered variants of the expression problem around the same time as Rice University's PLT, in particular Thomas Kühne<a href="#cite_note-K-8">[8]</a> in his dissertation, and Smaragdakis and Batory<a href="#cite_note-SB-9">[9]</a> in a parallel ECOOP 98 article.

Some follow-up work used the expression problem to showcase the power of programming language designs.<a href="#cite_note-Scala0-10">[10]</a><a href="#cite_note-Scala-11">[11]</a>

The expression problem is also a fundamental problem in multi-dimensional Software Product Line design and in particular as an application or special case of <a href="FOSD_program_cubes#Applications" title="FOSD program cubes">FOSD Program Cubes</a>.

<div class="mw-heading mw-heading2"><h2 id="Solutions">Solutions</h2></div>

There are various solutions to the expression problem. Each solution varies in the amount of code a user must write to implement them, and the language features they require.

<ul><li><a href="Multiple_dispatch" title="Multiple dispatch">Multiple dispatch</a><a href="#cite_note-Chambers_&_Leavens,_Multi-Methods-12">[12]</a></li>

<li><a href="Ruby_syntax#Open_classes" title="Ruby syntax">Ruby syntax § Open classes</a><a href="#cite_note-Clifton_et._al.,_MultiJava_Open_Classes-13">[13]</a></li>

<li><a href="Coproduct" title="Coproduct">Coproducts</a> of <a href="Functor" title="Functor">functors</a><a href="#cite_note-14">[14]</a></li>

<li><a href="Type_class" title="Type class">Type classes</a><a href="#cite_note-Wehr_&_Thiemann,_JavaGI_Type_Classes-15">[15]</a></li>

<li>Tagless-final<a href="#cite_note-Carette_et_al.,_Finally_tagless,_partially_evaluated:_Tagless_staged_interpreters_for_simpler_typed_languages-16">[16]</a> / Object algebras<a href="#cite_note-Oliveira_&_Cook,_Object_Algebras-17">[17]</a></li>

<li>Polymorphic Variants<a href="#cite_note-Code_Reuse_Through_Polymorphic_Variants-18">[18]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Problem_description">Problem description</h3></div>

We can imagine we do not have the source code for the following library, written in <a href="C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a>, which we wish to extend:

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr mw-highlight-lines" dir="ltr"><pre>interface IEvalExp

{

int Eval();

}

class Lit : IEvalExp

{

internal Lit(int n)

{

N = n;

}

internal int N { get; }

public int Eval()

{

return N;

}

}

class Add : IEvalExp

{

internal Add(IEvalExp left, IEvalExp right)

{

Left = left;

Right = right;

}

internal IEvalExp Left { get; }

internal IEvalExp Right { get; }

public int Eval()

{

return Left.Eval() + Right.Eval();

}

}

static class ExampleOne

{

static IEvalExp AddOneAndTwo() => new Add(new Lit(1), new Lit(2));

static int EvaluateTheSumOfOneAndTwo() => AddOneAndTwo().Eval();

}

</pre></div>

Using this library we can express the arithmetic expression <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">1 + 2</code> as we did in <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExampleOne.AddOneAndTwo()</code> and can evaluate the expression by calling <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">.Eval()</code>. Now imagine that we wish to extend this library, adding a new type is easy because we are working with an <a href="Object-oriented_programming" title="Object-oriented programming">Object-oriented programming language</a>. For example, we might create the following class:

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr mw-highlight-lines" dir="ltr"><pre>class Mult : IEvalExp

{

internal Mult(IEvalExp left, IEvalExp right)

{

Left = left;

Right = right;

}

public int Eval()

{

return Left.Eval() * Right.Eval();

}

}

</pre></div>

However, if we wish to add a new function over the type (a new method in C# terminology), for example to pretty print an expression, we have to change the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">IEvalExp</code> interface and then modify all the classes that implement the interface. Another possibility is to create a new interface that extends the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">IEvalExp</code> interface and then create sub-types for <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Lit</code>, <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Add</code> and <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">Mult</code> classes, but the expression returned in <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExampleOne.AddOneAndTwo()</code> has already been compiled so we will not be able to use the new function over the old type. The problem is reversed in functional programming languages like <a href="F_Sharp_(programming_language)" title="F Sharp (programming language)">F#</a> where it is easy to add a function over a given type, but extending or adding types is difficult.

<div class="mw-heading mw-heading3"><h3 id="Problem_solution_using_object_algebra">Problem solution using object algebra</h3></div>

Let us redesign the original library with extensibility in mind using the ideas from the paper Extensibility for the Masses.<a href="#cite_note-Oliveira_&_Cook,_Object_Algebras-17">[17]</a>

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr mw-highlight-lines" dir="ltr"><pre>interface ExpAlgebra<T>

{

T Lit(int n);

T Add(T left, T right);

}

class ExpFactory : ExpAlgebra<IEvalExp>

{

public IEvalExp Lit(int n)

{

return new Lit(n);

}

public IEvalExp Add(IEvalExp left, IEvalExp right)

{

return new Add(left, right);

}

}

static class ExampleTwo<T>

{

public static T AddOneToTwo(ExpAlgebra<T> ae) => ae.Add(ae.Lit(1), ae.Lit(2));

}

</pre></div>

We use the same implementation as in the first code example but now add a new interface containing the functions over the type as well as a factory for the algebra. Notice that we now generate the expression in <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExampleTwo.AddOneToTwo()</code> using the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExpAlgebra<T></code> interface instead of directly from the types. We can now add a function by extending the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExpAlgebra<T></code> interface, we will add functionality to print the expression:

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr mw-highlight-lines" dir="ltr"><pre>interface IPrintExp : IEvalExp

{

string Print();

}

class PrintableLit : Lit, IPrintExp

{

internal PrintableLit(int n) : base(n)

{

N = n;

}

public string Print()

{

return N.ToString();

}

}

class PrintableAdd : Add, IPrintExp

{

internal PrintableAdd(IPrintExp left, IPrintExp right) : base(left, right)

{

Left = left;

Right = right;

}

internal new IPrintExp Left { get; }

internal new IPrintExp Right { get; }

public string Print()

{

return Left.Print() + " + " + Right.Print();

}

}

class PrintFactory : ExpFactory, ExpAlgebra<IPrintExp>

{

public IPrintExp Add(IPrintExp left, IPrintExp right)

{

return new PrintableAdd(left, right);

}

public new IPrintExp Lit(int n)

{

return new PrintableLit(n);

}

}

static class ExampleThree

{

internal static int Evaluate() => ExampleTwo<IPrintExp>.AddOneToTwo(new PrintFactory()).Eval();

internal static string Print() => ExampleTwo<IPrintExp>.AddOneToTwo(new PrintFactory()).Print();

}

</pre></div>

Notice that in <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExampleThree.Print()</code> we are printing an expression that was already compiled in <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExampleTwo</code>, we did not need to modify any existing code. Notice also that this is still strongly typed, we do not need reflection or casting. If we would replace the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">PrintFactory()</code> with the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExpFactory()</code> in the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">ExampleThree.Print()</code> we would get a compilation error since the <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">.Print()</code> method does not exist in that context.

<ul><li><a href="FOSD_program_cubes#Applications" title="FOSD program cubes">Applications of FOSD program cubes</a></li>

<li><a href="Generic_programming" title="Generic programming">Generic programming</a></li>

<li><a href="POPLmark_challenge" title="POPLmark challenge">POPLmark challenge</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width reflist-columns-2">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt">"The Expression Problem"</a>.</cite>

</li>

<cite id="CITEREFReynolds1975" class="citation book cs1">Reynolds, John C. (1975). "User-defined Types and Procedural Data Structures as complementary approaches to Data Abstraction.". <a rel="nofollow" class="external text" href="https://www.cs.tufts.edu/~nr/cs257/archive/john-reynolds/procedural-data-structures.pdf">New Directions in Algorithmic Languages</a> (PDF). IFIP Working Group 2.1 on Algol. pp. 157–168.</cite>

</li>

<cite id="CITEREFCook1990" class="citation book cs1"><a href="William_Cook_(computer_scientist)" title="William Cook (computer scientist)">Cook, William</a> (1990). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/BFb0019443">"Object-Oriented Programming versus Abstract Data Types"</a>. In Bakker, J.W. de; Roever, W.P. de; Rozenberg, G. (eds.). Foundations of Object-Oriented Languages (FOOL), REX School/Workshop. Lecture Notes in Computer Science. Vol. 489. Noordwijkerhout, The Netherlands: Springer Berlin Heidelberg. pp. 151–178. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0019443">10.1007/BFb0019443</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-46450-1</bdi>.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://cs.brown.edu/~sk/Publications/Papers/Published/kff-synth-fp-oo/">"Synthesizing Object-Oriented and Functional Design to Promote Re-Use"</a>.</cite>

</li>

<cite id="CITEREFFindlerFlatt1999" class="citation journal cs1">Findler, Robert Bruce; Flatt, Matthew (1999). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F291251.289432">"Modular object-oriented programming with units and mixins"</a>. ACM SIGPLAN Notices. 34: 94–104. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F291251.289432">10.1145/291251.289432</a>.</cite>

</li>

<li id="cite_note-Mixins-6"><a href="#cite_ref-Mixins_6-0">^</a> <cite id="CITEREFCook1989" class="citation thesis cs1">Cook, William (1989). <a rel="nofollow" class="external text" href="https://www.cs.utexas.edu/~wcook/papers/thesis/cook89.pdf">A Denotational Semantics of Inheritance</a> (PDF) (PhD). Brown University.</cite>

</li>

<cite id="CITEREFFlattKrishnamurthiFelleisen1998" class="citation book cs1">Flatt, Matthew; Krishnamurthi, Shriram; Felleisen, Matthias (1998). "Classes and Mixins". Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '98. pp. 171–183. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F268946.268961">10.1145/268946.268961</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0897919791</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5815257">5815257</a>.</cite>

</li>

<cite id="CITEREFKühne1999" class="citation book cs1">Kühne, Thomas (1999). A Functional Pattern System for Object-Oriented Design. Darmstadt: Verlag Dr. Kovac. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-86064-770-7</bdi>.</cite>

</li>

<cite id="CITEREFSmaragdakisDon_Batory1998" class="citation book cs1">Smaragdakis, Yannis; Don Batory (1998). Implementing Reusable Object-Oriented Components. Lecture Notes in Computer Science. Vol. 1445.</cite>

</li>

<cite id="CITEREFZengerOdersky2001" class="citation book cs1">Zenger, Matthias; Odersky, Martin (2001). "Extensible Algebraic Datatypes with Defaults". Proceedings of the sixth ACM SIGPLAN international conference on Functional programming. pp. 241–252. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.6778">10.1.1.28.6778</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F507635.507665">10.1145/507635.507665</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58113-415-0</bdi>.</cite>

</li>

<cite id="CITEREFZengerOdersky2005" class="citation book cs1">Zenger, Matthias; Odersky, Martin (2005). <a rel="nofollow" class="external text" href="https://homepages.inf.ed.ac.uk/wadler/fool/program/final/10/10_Paper.pdf">"Independently extensible solutions to the expression problem"</a> (PDF). FOOL 2005. ACM. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.4449">10.1.1.107.4449</a>.</cite>

</li>

<li id="cite_note-Chambers_&_Leavens,_Multi-Methods-12"><a href="#cite_ref-Chambers_&_Leavens,_Multi-Methods_12-0">^</a> <cite id="CITEREFChambersLeavens1995" class="citation journal cs1">Chambers, Craig; Leavens, Gary T. (November 1995). <a rel="nofollow" class="external text" href="http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1036&context=cs_techreports">"Type Checking and Modules for Multi-Methods"</a>. ACM Transactions on Programming Languages and Systems. 17 (6): 805–843. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F218570.218571">10.1145/218570.218571</a>.</cite>

</li>

<li id="cite_note-Clifton_et._al.,_MultiJava_Open_Classes-13"><a href="#cite_ref-Clifton_et._al.,_MultiJava_Open_Classes_13-0">^</a> <cite id="CITEREFCliftonLeavensChambersMillstein2000" class="citation book cs1">Clifton, Curtis; Leavens, Gary T.; Chambers, Craig; Millstein, Todd (2000). "MultiJava: Modular open classes and symmetric multiple dispatch for Java". <a rel="nofollow" class="external text" href="http://people.csail.mit.edu/dnj/teaching/6898/papers/multijava.pdf">Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications</a> (PDF). pp. 130–145. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F353171.353181">10.1145/353171.353181</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58113-200-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7879645">7879645</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFWouter_Swierstra2008" class="citation journal cs1">Wouter Swierstra (2008). <a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0956796808006758">"Data Types à La Carte"</a>. <a href="Journal_of_Functional_Programming" title="Journal of Functional Programming">Journal of Functional Programming</a>. 18 (4). Cambridge University Press: 423–436. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0956796808006758">10.1017/S0956796808006758</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0956-7968">0956-7968</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:21038598">21038598</a>.</cite>

</li>

<li id="cite_note-Wehr_&_Thiemann,_JavaGI_Type_Classes-15"><a href="#cite_ref-Wehr_&_Thiemann,_JavaGI_Type_Classes_15-0">^</a> <cite id="CITEREFWehrThiemann2011" class="citation journal cs1">Wehr, Stefan; Thiemann, Peter (July 2011). <a rel="nofollow" class="external text" href="http://www.stefanwehr.de/publications/WehrThiemann2011TOPLAS.html">"JavaGI: The Interaction of Type Classes with Interfaces and Inheritance"</a>. ACM Transactions on Programming Languages and Systems. 33 (4): 1–83. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1985342.1985343">10.1145/1985342.1985343</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13174506">13174506</a>.</cite>

</li>

<li id="cite_note-Carette_et_al.,_Finally_tagless,_partially_evaluated:_Tagless_staged_interpreters_for_simpler_typed_languages-16"><a href="#cite_ref-Carette_et_al.,_Finally_tagless,_partially_evaluated:_Tagless_staged_interpreters_for_simpler_typed_languages_16-0">^</a> <cite id="CITEREFCaretteKiselyovChung-chieh2009" class="citation journal cs1">Carette, Jacques; Kiselyov, Oleg; Chung-chieh, Shan (2009). <a rel="nofollow" class="external text" href="http://okmij.org/ftp/tagless-final/JFP.pdf">"Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages"</a> (PDF). J. Funct. Program. 19 (5): 509–543. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0956796809007205">10.1017/S0956796809007205</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6054319">6054319</a>.</cite>

</li>

<li id="cite_note-Oliveira_&_Cook,_Object_Algebras-17">^ <a href="#cite_ref-Oliveira_&_Cook,_Object_Algebras_17-0">a</a> <a href="#cite_ref-Oliveira_&_Cook,_Object_Algebras_17-1">b</a> <cite id="CITEREFOliveiraCook2012" class="citation journal cs1">Oliveira, Bruno C. d. S.; Cook, William R. (2012). <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf">"Extensibility for the Masses: Practical Extensibility with Object Algebras"</a> (PDF). Ecoop '12.</cite>

</li>

<li id="cite_note-Code_Reuse_Through_Polymorphic_Variants-18"><a href="#cite_ref-Code_Reuse_Through_Polymorphic_Variants_18-0">^</a> <cite id="CITEREFGarrigue2000" class="citation book cs1">Garrigue, Jacques (2000). <a rel="nofollow" class="external text" href="https://www.math.nagoya-u.ac.jp/~garrigue/papers/variant-reuse.pdf">"Code Reuse Through Polymorphic Variants"</a> (PDF). Workshop on Foundations of Software Engineering. Sasaguri, Japan, November 2000. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.128.7169">10.1.1.128.7169</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt">The Expression Problem</a> by <a href="Philip_Wadler" title="Philip Wadler">Philip Wadler</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www.uni-koblenz.de/~laemmel/paradigms1011/resources/xproblem.html">Lecture: The Expression Problem</a> by Ralf Lämmell.</li>

<li><a rel="nofollow" class="external text" href="http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Dr-Ralf-Laemmel-Advanced-Functional-Programming-The-Expression-Problem">C9 Lectures: Dr. Ralf Lämmel - Advanced Functional Programming - The Expression Problem</a> at <a href="Channel_9_(discussion_forum)" class="mw-redirect" title="Channel 9 (discussion forum)">Channel 9</a>.</li>

<li><a rel="nofollow" class="external text" href="http://lampwww.epfl.ch/~odersky/papers/ExpressionProblem.html">Independently Extensible Solutions to the Expression Problem, Matthias Zenger and Martin Odersky, EPFL Lausanne</a>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-27" href="https://en.wikipedia.org/wiki/?title=Expression_problem&oldid=1302818812">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>